题解 P2864 【[USACO06JAN]树林The Grove】

发表于 | 更新于

$Description$

给定一张$R\times C$的地图，并给出一个联通块和一个起点，要求从起点出发，绕联通块一圈的最短路。

$Solution:$

设起点为$S$,从这个树林的第一行最左边的那个点向左连出一条射线，然后从$S$开始$bfs$，求穿越射线奇数次最后终点在$S$的最短路径即可。

以样例为例，

$Code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
#define ll long long
#define re register
#define inf 0x3f3f3f3f
using namespace std;
struct node{
    int x,y,p;
};
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
queue<node>q;
char s[60];
int n,m,ma[60][60],dis[60][60][2],xx,yy,sx,sy,dx[]={-1,-1,-1,0,0,1,1,1},dy[]={-1,0,1,-1,1,-1,0,1};
//dis[x][y][v]表示当前bfs的坐标为(x,y),穿越射线次数的奇偶性为v
inline bool across(node a,node b){
    if (a.x==xx&&a.y<yy&&xx>b.x)return 1;
    if (b.x==xx&&b.y<yy&&xx>a.x)return 1;
    return 0;
}//判断是否穿越射线
void bfs(){
    q.push((node){sx,sy,0});
    memset(dis,0x3f,sizeof(dis));dis[sx][sy][0]=0;
    while (!q.empty()){
        node u=q.front();int x=u.x,y=u.y,p=u.p;q.pop();
        for (int i=0;i<8;++i){
            int xx=x+dx[i],yy=y+dy[i];
            node v=(node){xx,yy,p};
            if (ma[xx][yy]==-1||xx<1||yy<1||xx>n||yy>m)continue;
            if (across(u,v))v.p^=1;
            if (dis[xx][yy][v.p]!=inf)continue;
            dis[xx][yy][v.p]=dis[x][y][p]+1;
            q.push(v);
        }
    }
}//bfs
signed main(){
    n=read(),m=read();
    for (int i=1;i<=n;++i){
        scanf("%s",s+1);
        for (int j=1;j<=m;++j)
            if (s[j]=='.')ma[i][j]=1;
            else if (s[j]=='*')ma[sx=i][sy=j]=1;
            else{if (!xx)xx=i,yy=j;ma[i][j]=-1;}
    }
    bfs();
    printf("%d",dis[sx][sy][1]);
    return 0;
}